package Leetcode.图;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TopologicalSort {

    // 顶点的类
    static class Vertex {
        int label;
        List<Vertex> adjacentVertices = new ArrayList<>();

        Vertex(int label) {
            this.label = label;
        }
    }

    // 拓扑排序函数
    public List<Vertex> topologicalSort(List<Vertex> vertices) {
        List<Vertex> sortedList = new ArrayList<>();
        Queue<Vertex> queue = new LinkedList<>();
        int[] inDegree = new int[vertices.size()];

        // 初始化所有顶点的入度
        for (Vertex vertex : vertices) {
            for (Vertex adjacentVertex : vertex.adjacentVertices) {
                inDegree[adjacentVertex.label]++;
            }
        }

        // 将所有入度为0的顶点加入队列
        for (Vertex vertex : vertices) {
            if (inDegree[vertex.label] == 0) {
                queue.add(vertex);
            }
        }

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            sortedList.add(vertex);

            // 遍历所有相邻的顶点
            for (Vertex adjacentVertex : vertex.adjacentVertices) {
                // 减少相邻顶点的入度
                inDegree[adjacentVertex.label]--;
                // 如果相邻顶点的入度为0，则将其加入队列
                if (inDegree[adjacentVertex.label] == 0) {
                    queue.add(adjacentVertex);
                }
            }
        }

        // 如果排序后的顶点数不等于图中顶点数，则说明图中有环
        if (sortedList.size() != vertices.size()) {
            throw new RuntimeException("图中有环，无法进行拓扑排序");
        }

        return sortedList;
    }

    /**
     * 判断拓扑排序是否唯一
     */
    public static boolean isUniqueTopologicalSort(int vertices, List<List<Integer>> adj) {
        int[] inDegree = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            for (int neighbor : adj.get(i)) {
                inDegree[neighbor]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0; // 用于记录每一步中入度为0的顶点数量
        while (!queue.isEmpty()) {
            if (queue.size() > 1) {
                // 如果在任何一步中有多个入度为0的顶点，则拓扑排序不唯一
                return false;
            }
            int vertex = queue.poll();
            count++;
            for (int neighbor : adj.get(vertex)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // 如果拓扑排序的顶点数量等于图中的顶点数量，则拓扑排序是有效的
        // 但是这里我们只关心是否唯一，所以不需要这个检查
        return count == vertices;
    }

    public static void main(String[] args) {
        // 创建顶点
        Vertex v0 = new Vertex(0);
        Vertex v1 = new Vertex(1);
        Vertex v2 = new Vertex(2);
        Vertex v3 = new Vertex(3);
        Vertex v4 = new Vertex(4);

        // 构建图的边
        v0.adjacentVertices.add(v1);
        v0.adjacentVertices.add(v2);
        v1.adjacentVertices.add(v3);
        v2.adjacentVertices.add(v3);
        v3.adjacentVertices.add(v4);

        List<Vertex> vertices = new ArrayList<>();
        vertices.add(v0);
        vertices.add(v1);
        vertices.add(v2);
        vertices.add(v3);
        vertices.add(v4);

        TopologicalSort ts = new TopologicalSort();
        List<Vertex> sortedVertices = ts.topologicalSort(vertices);

        System.out.println("拓扑排序结果：");
        for (Vertex vertex : sortedVertices) {
            System.out.print(vertex.label + " ");
        }

        int n = 6;
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // 构建图的邻接表
        adj.get(5).add(2);
        adj.get(5).add(0);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);

        boolean unique = isUniqueTopologicalSort(n, adj);
        System.out.println();
        System.out.println("拓扑排序是否唯一: " + unique);
    }
}
